﻿#define _CRT_SECURE_NO_WARNINGS 1
//给定⼀个整数数组nums和⼀个整数k，返回其中元素之和可被k整除的（连续、⾮空）⼦数组的数⽬。
//⼦数组是数组的连续部分。
//eg：输⼊：nums = [4, 5, 0, -2, -3, 1], k = 5  输出：7
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int subarraysDivByK(vector<int> nums,int k)
{
	unordered_map<int, int> hash;
	hash[0 % k] = 1;
	// 0 这个数的余数
	int sum = 0, ret = 0;
	for (auto x : nums)
	{
		sum += x;
		// 算出当前位置的前缀和
		int r = (sum % k + k) % k;
		// 修正后的余数
		if (hash.count(r)) ret += hash[r];
		// 统计结果
		hash[r]++;
	}
	return ret;
}

int main()
{
	vector<int> nums = { 4, 5, 0, -2, -3, 1 };
	int k = 5;
	int an = subarraysDivByK(nums,k);
	cout << an << endl;

	return 0;
}